#include "headfiles.h"

NODE *removeNthFromEnd(NODE *head, int n) {
    NODE *pre, *cur;
    pre = NULL;
    cur = head;
    int index = 0;
    while (cur && index < n) {
        cur = cur->next;
        index++;
    }
    
    pre = head;
    while (cur) {
        cur = cur->next;
        pre = pre->next;
    }
    
    if (pre == head) {
        head = pre->next;
        delete pre;
    }
    else {
        NODE *node = pre->next;
        pre->next = node->next;
        delete node;
    }
    
    return head;
}
